#pragma once
#include <cstddef>
#include <iostream>
#include <ostream>
#include <utility>
#include <vector>
class Date
{
public:
    Date(int year = 1900, int month = 1, int day = 1)
        : year_(year)
        , month_(month)
        , day_(day)
    {}
    bool operator<(const Date &d) const
    {
        return (year_ < d.year_) || (year_ == d.year_ && month_ < d.month_)
               || (year_ == d.year_ && month_ == d.month_ && day_ < d.day_);
    }
    bool operator>(const Date &d) const
    {
        return (year_ > d.year_) || (year_ == d.year_ && month_ > d.month_)
               || (year_ == d.year_ && month_ == d.month_ && day_ > d.day_);
    }
    friend std::ostream &operator<<(std::ostream &cout_, const Date &d);

private:
    int year_;
    int month_;
    int day_;
};

std::ostream &operator<<(std::ostream &cout_, const Date &d)
{
    cout_ << d.year_ << "-" << d.month_ << "-" << d.day_ << std::endl;
    return cout_;
}

struct PDateLess
{
    bool operator()(const Date *p1, const Date *p2)
    {
        return *p1 < *p2;
    }
};

template<class T>
class Less
{
public:
    bool operator()(const T &x, const T &y)
    {
        return x < y;
    }
};

template<class T>
class Greater
{
public:
    bool operator()(const T &x, const T &y)
    {
        return x > y;
    }
};

// // 特化
// template<>
// class Less<Date *>
// {
// public:
//     bool operator()(Date *const &x, Date *const &y)
//     {
//         return *x < *y;
//     }
// };

// 偏特化
template<class T>
class Less<T *>
{
public:
    bool operator()(T *const &x, T *const &y)
    {
        return x < y;
    }
};

namespace canoe
{
    template<class T, class Container = std::vector<T>, class Compare = Less<T>>
    class priority_queue
    {
    public:
        priority_queue() = default;
        template<class InputIterator>
        priority_queue(InputIterator first, InputIterator last)
            : con_(first, last)
        {
            for (size_t i = (con_.size() - 1 - 1) / 2; i >= 0; --i)
            {
                adjust_down(i);
            }
        }
        void adjust_up(int child)
        {
            Compare com;
            int parent = (child - 1) / 2;
            while (child > 0)
            {
                // if (con_[child] > con_[parent])
                if (com(con_[child], con_[parent]))
                {
                    std::swap(con_[child], con_[parent]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                    break;
            }
        }
        void adjust_down(int parent)
        {
            int child = parent * 2 + 1;
            while (child < con_.size())
            {
                if (child + 1 < con_[child + 1] > con_[child])
                    ++child;
                if (con_[child] > con_[parent])
                {
                    std::swap(con_[child], con_[parent]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                    break;
            }
        }
        void push(const T &value)
        {
            con_.push_back(value);
            adjust_up(con_.size() - 1);
        }
        bool empty() const
        {
            return con_.empty();
        }
        T top()
        {
            return con_.back();
        }
        void pop()
        {
            con_.pop_back();
        }
        ~priority_queue()
        {}

    private:
        Container con_;
    };
} // namespace canoe